排队打水

题目 排队打水

思路分析

大概算是个短作业优先的问题

直觉上的做法就是 需要时间少的先做呗

用优先队列，因为放入队列时会自动把最小的放到队列最前面，越往后数越大。

如果第一个人去接水，后面的人都要等待他的节水时间，所以res要加上：第一个人的节水时间*后面的人数。（代码中为x * t）

证明一下正确性：

代码实现

优先队列：

#include<bits/stdc++.h>

using namespace std;

priority_queue<int,vector<int>,greater<int>> heap;

int n;

int main()

{

    cin>>n;

    for(int i=1;i<=n;i++){

        int x;cin>>x;

        heap.push(x);

    }

    long long res=0;

    int later=n-1;

    while(later){

        int time=heap.top();

        heap.pop();

        res+=later*time;

        later--;

    }

    cout<<res;

    return 0;

}

前缀和

//假如现在轮到第i个人打水，那么他的等待时间为所有在他前面打水的人的打水时间之和，所以可以排序后记录前缀和，最后用for循环累加答案.

#include <bits/stdc++.h>

using namespace std;

const int N = 100010;

int n;

int a[N];

long long w[N];

int main()

{

    cin >> n;

    for(int i = 1;i <= n;i++)

        cin >> a[i];

    sort(a+1, a+1+n);

    for(int i = 1;i <= n;i++)

        w[i] = w[i-1]+a[i];

    long long res = 0;

    for(int i = 1;i < n;i++)

        res += w[i];

    cout << res;

    return 0;

}

同类题型

视频讲解

⬅️ 排序 权贪心（短作业优先 重权值优先） 🏠 00-刷题理模型 ➡️ 最小消耗